package main.java.indi.zyj.c150.sort;

import main.java.indi.zyj.utils.Utils;

/**
 *      快排
 *
 */
public class _01_QuickSort {

    public static void main(String[] args) {
        int[] randomArr = Utils.getRandomArr(10, 0, 20);
        Utils.print(randomArr);
        QuickSort(randomArr, 0, randomArr.length - 1);
        Utils.print(randomArr);

    }


    private static void QuickSort(int[] arr, int p, int r){
        if (p < r){
            int q = Partition1(arr, p, r);
            QuickSort(arr, q+1, r);
            QuickSort(arr, p, q-1);
        }
    }

    /**
     *      快排，单向扫描分区
     *
     */
    private static int Partition0(int[] arr, int p, int r){

        int pivot = arr[p];
        int q = p+1;
        int rear = r;
        while (q <= rear){
            if (arr[q] <= pivot){
                q++;
            }else {
                Utils.swap(arr, q, rear);
                rear--;
            }
        }

        Utils.swap(arr, p, rear);

        return rear;
    }

    /**
     *      快排，双向扫描分区
     *
     */
    private static int Partition1(int[] arr, int p, int r){

        int pivot = arr[p];
        int q = p+1;
        int rear = r;
        while (q < rear){
            while (q <= rear && arr[q] <= pivot)    q++;
            while (q <= rear && arr[rear] > pivot)    rear--;
            if (q < rear){
                Utils.swap(arr, q, rear);
            }
        }

        Utils.swap(arr, p, rear);

        return rear;
    }


    /**
     *      快排，三指针单向扫描分区
     *
     *
     */
    private static void sort(int[] array, int start, int end) {
        //初始化三指针
        //小于主元的指针和等于主元的指针都初始化为下标为数组第二个
        //大于主元的指针初始化为尾元
        int smaller = start+1;
        int equal = smaller;
        int bigger = end;
        //设置退出条件
        if(smaller > bigger) return ;
        //选择主元，一般为首元
        int num = array[start];
        /*
         * 当smaller扫描到的数字小于主元，则下标为smaller和equal的需要交换数据，这样就又将小于主元的放在一起了，然后smaller和equal都要自增
         * 当smaller扫描到的数字等于主元，直接将smaller自增
         * 当smaller扫描到的数字大于主元，就将小标为smaller和bigger上的数据交换，bigger再自减(和单向扫描分区法处理一样）
         */
        while(smaller <= bigger) {
            if(array[smaller] < num) {
                Utils.swap(array, equal, smaller);
                equal++;
                smaller++;
            }
            else if(array[smaller] == num) {
                smaller++;
            }
            else if(array[smaller] > num) {
                Utils.swap(array, smaller, bigger);
                bigger--;
            }
        }
        //交换首元与right上的数
        Utils.swap(array, start, equal-1);
        //继续将right两边的数组进行快速排序
        sort(array, start, equal-2);
        sort(array, bigger+1, end);
    }
}
